{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #冗余连接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findRedundantConnection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #冗余连接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>树可以看成是一个连通且 <strong>无环&nbsp;</strong>的&nbsp;<strong>无向&nbsp;</strong>图。</p>\n",
    "\n",
    "<p>给定往一棵&nbsp;<code>n</code> 个节点 (节点值&nbsp;<code>1～n</code>) 的树中添加一条边后的图。添加的边的两个顶点包含在 <code>1</code> 到 <code>n</code>&nbsp;中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 <code>n</code> 的二维数组 <code>edges</code>&nbsp;，<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示图中在 <code>ai</code> 和 <code>bi</code> 之间存在一条边。</p>\n",
    "\n",
    "<p>请找出一条可以删去的边，删除后可使得剩余部分是一个有着 <code>n</code> 个节点的树。如果有多个答案，则返回数组&nbsp;<code>edges</code>&nbsp;中最后出现的边。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626676174-hOEVUL-image.png\" style=\"width: 152px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[1,2],[1,3],[2,3]]\n",
    "<strong>输出:</strong> [2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode-cn.com/1626676179-kGxcmu-image.png\" style=\"width: 250px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]\n",
    "<strong>输出:</strong> [1,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= ai&nbsp;&lt; bi&nbsp;&lt;= edges.length</code></li>\n",
    "\t<li><code>ai != bi</code></li>\n",
    "\t<li><code>edges</code> 中无重复元素</li>\n",
    "\t<li>给定的图是连通的&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 684&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/redundant-connection/\">https://leetcode-cn.com/problems/redundant-connection/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [7LpjUW](https://leetcode.cn/problems/7LpjUW/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [7LpjUW](https://leetcode.cn/problems/7LpjUW/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2],[1,3],[2,3]]', '[[1,2],[2,3],[3,4],[1,4],[1,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [0]*(len(edges)+1)\n",
    "        for i in range(len(edges)):\n",
    "            parent[i] = i\n",
    "        def find(index):\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "\n",
    "        def union(index1, index2):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for e in edges:\n",
    "            if find(e[0]) != find(e[1]):\n",
    "                union(e[0], e[1])\n",
    "            else:\n",
    "                return e\n",
    "        return []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        f=[i for i in range(1,n+1)]\n",
    "        def find(x):   # 查找根节点\n",
    "            while f[x-1]!=x:\n",
    "                x=f[x-1]\n",
    "            return x   \n",
    "        for [i,j] in edges:\n",
    "            if find(i)==find(j):  # 如果两个节点属于同一个子集，则该[i,j]再加上去肯定闭合，故返回[i,j]\n",
    "                return [i,j]\n",
    "            else:\n",
    "                f[find(j)-1]=find(i)  # 如果不在同一个子集，则合并节点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        pre = list(range(n + 1))\n",
    "        res = []\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            while x != pre[x]:\n",
    "                x = pre[x]\n",
    "            while y != pre[y]:\n",
    "                y = pre[y]\n",
    "            if x == y:\n",
    "                res = edge\n",
    "            pre[x] = y \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(x):\n",
    "            if f[x] != x: f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            f[find(x)] = find(y)\n",
    "        \n",
    "        n = len(edges)\n",
    "        f = list(range(n + 1))\n",
    "\n",
    "        ans = []\n",
    "        for u, v in edges:\n",
    "            if find(u) == find(v):\n",
    "                ans = [u, v]\n",
    "            else:\n",
    "                union(u, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        f = [i for i in range(n)]\n",
    "        for e in edges[:-1]:\n",
    "            f0 = self.get_father(f, e[0] - 1)\n",
    "            f1 = self.get_father(f, e[1] - 1)\n",
    "            if f0 == f1:\n",
    "                return e\n",
    "            f[f1] = f0\n",
    "        return edges[-1]\n",
    "\n",
    "    def get_father(self, f: List[int], x: int) -> int:\n",
    "        nodes = []\n",
    "        while x != f[x]:\n",
    "            nodes.append(x)\n",
    "            x = f[x]\n",
    "        for n in nodes:\n",
    "            f[n] = x\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def _init_data_structure_(self, n):\n",
    "        # 注意正确初始化\n",
    "        self.father = [i for i in range(n+1)]\n",
    "\n",
    "    def join(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v: return\n",
    "        else: self.father[v] = u\n",
    "\n",
    "    def find(self, u):\n",
    "        # 在find的过程中逐步把父节点调为顶层父节点，在此之前不能认为self.father都是正确的顶层父节点\n",
    "        if u == self.father[u]: return u\n",
    "        self.father[u] = self.find(self.father[u])\n",
    "        return self.father[u]\n",
    "\n",
    "    def isSame(self, u, v):\n",
    "        return self.find(u) == self.find(v)\n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        self._init_data_structure_(n)\n",
    "        for i in range(n):\n",
    "            if self.isSame(edges[i][0], edges[i][1]): return edges[i]\n",
    "            else: self.join(edges[i][0], edges[i][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        parent = [i for i in range(len(edges)+1)]\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def merge(x, y):\n",
    "            fx = find(x)\n",
    "            fy = find(y)\n",
    "            if fx != fy:\n",
    "                parent[fy] = fx\n",
    "\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            if find(x) != find(y):\n",
    "                merge(x, y)\n",
    "            else:\n",
    "                return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "    n = len(edges)\n",
    "    fa = [i for i in range(n + 1)]\n",
    "\n",
    "    def find(x):\n",
    "      if fa[x] == x: return x\n",
    "      else:\n",
    "        fa[x] = find(fa[x])\n",
    "        return fa[x]\n",
    "    \n",
    "    def union(i, j):\n",
    "      fa[find(i)] = find(j)\n",
    "    \n",
    "    for i, j in edges:\n",
    "      if find(i) != find(j): union(i, j)\n",
    "      else: return [i, j]\n",
    "\n",
    "    return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "    c = defaultdict(lambda:0)\n",
    "    m = 1\n",
    "    for a, b in edges:\n",
    "      if c[a] == c[b]:\n",
    "        # print(f\"a {a} {b} c {c[a]} {c[b]}\")\n",
    "        if c[a] != 0:\n",
    "          return [a, b]\n",
    "        else:\n",
    "          # print(f\"init {a} {b} {m}\")\n",
    "          c[a] = m\n",
    "          c[b] = m\n",
    "          m += 1\n",
    "      else:\n",
    "        if 0 == c[a]:\n",
    "          c[a] = c[b]\n",
    "        elif 0 == c[b]:\n",
    "          c[b] = c[a]\n",
    "        else:\n",
    "          # print(f\"fillall from {a} {b} {m}\")\n",
    "          c1 = c[a]\n",
    "          c2 = c[b]\n",
    "          for k in c.keys():\n",
    "            if c[k] == c1:\n",
    "              c[k] = c2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, u, v):\n",
    "        fu = self.find(u)\n",
    "        fv = self.find(v)\n",
    "        if fu == fv:\n",
    "            return\n",
    "        self.parent[fv] = fu\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n+1)\n",
    "        ans = []\n",
    "        for u, v in edges:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans = [u, v]\n",
    "            else:\n",
    "                uf.union(u, v)\n",
    "        return ans\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        fa = [i for i in range(n + 1)]\n",
    "        def find(x:int) -> int:\n",
    "            if x == fa[x]: return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x:int, y:int) -> None:\n",
    "            x, y = find(x), find(y)\n",
    "            fa[x] = y\n",
    "\n",
    "        def check(x:int, y:int) -> bool:\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            if check(x, y):\n",
    "                return edge\n",
    "            merge(x, y)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        f = [i for i in range(len(edges)+1)]\n",
    "        def find(x):\n",
    "            if x == f[x]:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        for e in edges:\n",
    "            e1, e2 = find(e[0]), find(e[1])\n",
    "            if e1 == e2:\n",
    "                return e\n",
    "            else:\n",
    "                f[e1] = f[e2]\n",
    "        \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        # 找祖先\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        # 合并祖先\n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))  # 初始化节点的父节点列表\n",
    "\n",
    "        def find(index):  # 查找节点的根节点（根节点的特点是 parent[root] = root,即该节点的父节点是其本身）\n",
    "            if parent[index] != index:    # 该节点的父节点是其本身\n",
    "                \n",
    "            # else:\n",
    "                parent[index] = find(parent[index])  # 递归查找根节点，将节点的父节点更新为根节点\n",
    "            return parent[index]      # 返回根节点\n",
    "\n",
    "        def union(index1, index2):              # 合并两个节点所在的集合，能合并说明，有共同的根，既然是相同的根，那么更新其根\n",
    "            parent[find(index1)] = find(index2) # 更新该节点的根\n",
    "\n",
    "\n",
    "        for node1, node2 in edges:  # 遍历每条边\n",
    "            if find(node1) != find(node2):  # 如果两个节点不在同一个集合中\n",
    "                union(node1, node2)  # 合并它们的集合\n",
    "            else:\n",
    "                return [node1, node2]  # 如果它们已经在同一个集合中，返回冗余边\n",
    "\n",
    "        return []  # 如果遍历完所有边都没有找到冗余边，返回空列表表示没有冗余边"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        fa = [i for i in range(n + 1)]\n",
    "        rk = [1 for i in range(n + 1)]\n",
    "\n",
    "        def find(x:int) -> int:\n",
    "            if x == fa[x]: return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x:int, y:int) -> None:\n",
    "            x, y = find(x), find(y)\n",
    "            if rk[x] < rk[y]:\n",
    "                fa[x] = y\n",
    "            else:\n",
    "                if fa[x] == fa[y]:\n",
    "                    rk[y] += 1\n",
    "                fa[y] = x\n",
    "\n",
    "        def check(x:int, y:int) -> bool:\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        for edge in edges:\n",
    "            x, y = edge\n",
    "            if check(x, y):\n",
    "                return edge\n",
    "            merge(x, y)\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        while x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self, u, v):\n",
    "        fu = self.find(u)\n",
    "        fv = self.find(v)\n",
    "        if fu == fv:\n",
    "            return\n",
    "        self.parent[fv] = fu\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n+1)\n",
    "        ans = []\n",
    "        for u, v in edges:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans = [u, v]\n",
    "            else:\n",
    "                uf.union(u, v)\n",
    "        return ans\n",
    "    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n + 1)]\n",
    "        self.rank = [0] * (n + 1)\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "\n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "\n",
    "        if self.rank[rootX] > self.rank[rootY]:\n",
    "            self.parent[rootY] = rootX\n",
    "        elif self.rank[rootX] < self.rank[rootY]:\n",
    "            self.parent[rootX] = rootY\n",
    "        else:\n",
    "            self.parent[rootY] = rootX\n",
    "            self.rank[rootX] += 1\n",
    "\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        for edge in edges:\n",
    "            if not uf.union(edge[0], edge[1]):\n",
    "                return edge\n",
    "\n",
    "# Example\n",
    "edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]\n",
    "s = Solution()\n",
    "print(s.findRedundantConnection(edges))  # Output: [1,4]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        class UF:\n",
    "            def __init__(self,n):\n",
    "                self.count=n\n",
    "                self.parent=[i for i in range(n)]\n",
    "            def find(self,p):\n",
    "                if self.parent[p]!=p:\n",
    "                    self.parent[p]=self.find(self.parent[p])\n",
    "                return self.parent[p]\n",
    "            def connected(self,p,q):\n",
    "                rootP=self.find(p)\n",
    "                rootQ=self.find(q)\n",
    "                return rootP==rootQ\n",
    "            def union(self,p,q):\n",
    "                rootP=self.find(p)\n",
    "                rootQ=self.find(q)\n",
    "                if rootP==rootQ:\n",
    "                    return False\n",
    "                self.parent[rootP]=rootQ\n",
    "                self.count-=1\n",
    "                return True\n",
    "        uf=UF(len(edges))\n",
    "        for i in edges:\n",
    "            if not uf.union(i[0]-1,i[1]-1):\n",
    "                return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        ### prim\n",
    "        # n = len(edges)\n",
    "        # from collections import defaultdict\n",
    "        # import heapq\n",
    "        # import copy\n",
    "        # edge_q = []\n",
    "        # graph = defaultdict(list)\n",
    "        # for w, e in enumerate(edges): #### 权重\n",
    "        #     graph[e[0]].append([e[1], w])\n",
    "        #     graph[e[1]].append([e[0], w])\n",
    "\n",
    "        \n",
    "        # visited = [False] * n\n",
    "        # edges_copy = copy.deepcopy(edges) \n",
    "        # for i in range(n):\n",
    "        #     if not visited[i]:\n",
    "        #         visited[i] = True\n",
    "        #         for neighbor in graph[i+1]:\n",
    "        #             if not visited[neighbor[0]-1]:\n",
    "        #                 triple = [neighbor[1], i+1, neighbor[0]]\n",
    "        #                 heapq.heappush(edge_q, triple)\n",
    "                    \n",
    "        #         while len(edge_q):\n",
    "        #             triple = heapq.heappop(edge_q)\n",
    "        #             if visited[triple[2]-1]:\n",
    "        #                 continue\n",
    "                    \n",
    "        #             visited[triple[2]-1] = True\n",
    "        #             edges_copy.remove([min(triple[1:]), max(triple[1:])])\n",
    "        #             node =  triple[2]\n",
    "        #             for neighbor in graph[node]:\n",
    "        #                 if not visited[neighbor[0]-1]:\n",
    "        #                     triple = [neighbor[1], node, neighbor[0]]\n",
    "        #                     heapq.heappush(edge_q, triple)\n",
    "        \n",
    "        # return edges_copy[0]\n",
    "\n",
    "\n",
    "        #### kruskal\n",
    "        # n = len(edges)\n",
    "        # set_color = [i for i in range(n)]\n",
    "        # color_dict = {i: [i+1] for i in range(n)}\n",
    "        # import heapq\n",
    "        # edge_q = [[i, e] for i, e in enumerate(edges)]\n",
    "        # heapq.heapify(edge_q)\n",
    "        # while len(edge_q):\n",
    "        #     e = heapq.heappop(edge_q)[1]\n",
    "        #     if set_color[e[0]-1] == set_color[e[1]-1]:\n",
    "        #         continue\n",
    "        #     color0 = set_color[e[0]-1]\n",
    "        #     color1 = set_color[e[1]-1]\n",
    "        #     if len(color_dict[color1]) > len(color_dict[color0]):\n",
    "        #         for n in color_dict[color0]:\n",
    "        #             set_color[n-1] = color1\n",
    "        #         color_dict[color1].extend(color_dict.pop(color0))\n",
    "        #     else:\n",
    "        #         for n in color_dict[color1]:\n",
    "        #             set_color[n-1] = color0\n",
    "        #         color_dict[color0].extend(color_dict.pop(color1))\n",
    "\n",
    "        #     edges.remove(e)\n",
    "        \n",
    "        # return edges[0]\n",
    "\n",
    "        ### Union Find\n",
    "        def find(p):\n",
    "            while parent[p] != p:\n",
    "                p = parent[p]\n",
    "            \n",
    "            return p\n",
    "\n",
    "        def union(p, q):\n",
    "            root_p = find(p)\n",
    "            root_q = find(q)\n",
    "            if root_p == root_q:\n",
    "                return True\n",
    "            else:\n",
    "                parent[root_p] = root_q\n",
    "\n",
    "        n = len(edges)\n",
    "        parent = [i for i in range(n+1)]\n",
    "        for e in edges:\n",
    "            connected = union(e[0], e[1])\n",
    "            if connected:\n",
    "                return e\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, fa: [int], p: int) -> int:\n",
    "        if fa[p] == p:\n",
    "            return fa[p]\n",
    "        fa[p] = self.find(fa, fa[p])\n",
    "        return fa[p]\n",
    "\n",
    "    def merge(self, fa: [int], p: int, q: int):\n",
    "        pp = self.find(fa, p)\n",
    "        qq = self.find(fa, q)\n",
    "        if pp == qq: return \n",
    "        if pp < qq:\n",
    "            fa[qq] = pp\n",
    "        else:\n",
    "            fa[pp] = qq\n",
    "        \n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        fa = [i for i in range(n)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            fa = [k for k in range(n)]\n",
    "            # print(\"ignore :\", edges[i])\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                # u, v = edges[j][0] - 1, edges[j][1] - 1\n",
    "                # print(edges[j], u, v, edges[j][0], edges[j][1])\n",
    "                self.merge(fa, edges[j][0] - 1, edges[j][1] - 1)\n",
    "                # print(fa)\n",
    "            \n",
    "            s = set([self.find(fa, k) for k in range(n)])\n",
    "            # print(edges[i], s)\n",
    "            if len(s) == 1:\n",
    "                return edges[i]\n",
    "        return edges[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        u = [-1] * (n + 1)\n",
    "        def Find(u:List[int] , x:int)->int:\n",
    "            if u[x] < 0:\n",
    "                return x;\n",
    "            u[x] = Find(u , u[x])\n",
    "            return u[x]\n",
    "        for x , y in edges:\n",
    "            px , py = Find(u , x) , Find(u , y)\n",
    "            if(px == py):\n",
    "                return [x , y]\n",
    "            else:\n",
    "                if(u[px] > u[py]):\n",
    "                    px , py = py , px\n",
    "                u[px] += u[py]\n",
    "                u[py] = px"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.len = len(edges)+1\n",
    "        self.fathers = [None for _ in range(self.len)]\n",
    "        for i in range(self.len):\n",
    "            self.fathers[i] = i\n",
    "        for edge in edges:\n",
    "            if self.findfather(edge[0])!=self.findfather(edge[1]):\n",
    "                self.union(edge[0], edge[1])\n",
    "            else:\n",
    "                return edge\n",
    "\n",
    "    def findfather(self, node):\n",
    "        if self.fathers[node]!=node:\n",
    "            self.fathers[node] = self.findfather(self.fathers[node])\n",
    "        return self.fathers[node]\n",
    "\n",
    "    def union(self, i, j):\n",
    "        father_of_i = self.findfather(i)\n",
    "        father_of_j = self.findfather(j)\n",
    "        if father_of_i!=father_of_j:\n",
    "            self.fathers[father_of_i]=father_of_j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.n = len(edges)\n",
    "        self.fathers = [None]\n",
    "        for i in range(1,self.n+1):\n",
    "            self.fathers.append(i)\n",
    "        for edge in edges:\n",
    "            if not self.union(edge[0], edge[1]):\n",
    "                return edge\n",
    "\n",
    "        return []\n",
    "\n",
    "\n",
    "    def union(self, dot1, dot2):\n",
    "        father_1 = self.findfather(dot1)\n",
    "        father_2 = self.findfather(dot2)\n",
    "        if father_1!=father_2:\n",
    "            self.fathers[father_1] = father_2\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def findfather(self, dot):\n",
    "        if self.fathers[dot]!=dot:\n",
    "            self.fathers[dot] = self.findfather(self.fathers[dot])\n",
    "        return self.fathers[dot]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        # 并 查 集\n",
    "        # 新加入的点为上一个根节点的最新父节点\n",
    "        # n 条 边\n",
    "        # 最后出现的边 == 出现环 == 有着相同的根节点\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "        # 查找根节点\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        # 合并（改变父节点），新加入的一组点的根节点为原来的一组点的根节点的最新父节点\n",
    "        def union(index1: int, index2: int):\n",
    "            # 对两个根节点合并\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        # [[1,2],[1,3],[2,3]]\n",
    "        # [1,2]1的父节点变成2，[1,3]2的父节点变成3，[2,3]2、3有相同的父节点，返回[2,3]\n",
    "        for node1, node2 in edges:\n",
    "            # 未加入\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent, rank = list(range(n)), [1] * n \n",
    "        def myFind(i):\n",
    "            if i != parent[i]:\n",
    "                parent[i] = myFind(parent[i])\n",
    "            return parent[i]\n",
    "        def myUnion(i, j):\n",
    "            pi, pj = myFind(i), myFind(j)\n",
    "            if pi == pj: return\n",
    "            if rank[pi] > rank[pj]:\n",
    "                parent[pj] = pi\n",
    "            elif rank[pi] < rank[pj]:\n",
    "                parent[pi] = pj\n",
    "            else:\n",
    "                parent[pj] = pi\n",
    "                rank[pi] += 1\n",
    "            return\n",
    "        for i, j in edges:\n",
    "            pi, pj = myFind(i - 1), myFind(j - 1)\n",
    "            if pi == pj:\n",
    "                return [i, j]\n",
    "            myUnion(pi, pj)\n",
    "        return [0, 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "                x = p[x]\n",
    "            return p[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            p[find(y)] = find(x)\n",
    "        \n",
    "        def isconnected(x, y):\n",
    "            return find(x) == find(y)\n",
    "        \n",
    "        ans = []\n",
    "        for a, b in edges:\n",
    "            if not isconnected(a-1, b-1):\n",
    "                union(a-1, b-1)\n",
    "            else:\n",
    "                ans = [a, b]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        degrees = [0] * (n+1)\n",
    "        adjacent = [[] for _ in range(n+1)]\n",
    "        for i,j in edges:\n",
    "            degrees[i] += 1\n",
    "            degrees[j] += 1\n",
    "            adjacent[i].append(j)\n",
    "            adjacent[j].append(i)\n",
    "\n",
    "        queue = deque()\n",
    "        for i in range(n+1):\n",
    "            if degrees[i] == 1:\n",
    "                queue.append(i)\n",
    "        \n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for neighbor in adjacent[node]:\n",
    "                degrees[node] -= 1\n",
    "                degrees[neighbor] -= 1\n",
    "                if degrees[neighbor] == 1:\n",
    "                    queue.append(neighbor)\n",
    "        for i,j in edges[::-1]:\n",
    "            if degrees[i] > 1 and degrees[j] > 1:\n",
    "                return [i,j]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n+1))\n",
    "\n",
    "        def find(index):\n",
    "            if parent[index]!=index:\n",
    "                parent[index]=find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1,index2):\n",
    "            parent[find(index1)]=find(index2)\n",
    "        \n",
    "        for node1,node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1,node2)\n",
    "            else:\n",
    "                return [node1,node2]\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        kkk=setUnion(n+1)\n",
    "        for i,j in edges:\n",
    "            if kkk.find(i)==kkk.find(j): return [i,j]\n",
    "            kkk.union(i,j)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        def find(x):\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            else:\n",
    "                fa[x]=find(fa[x])\n",
    "                return fa[x]\n",
    "        \n",
    "        def union(x,y):\n",
    "            u,v=find(x),find(y)\n",
    "            fa[u]=v\n",
    "        fa=[i for i in range(len(edges))]\n",
    "        res=[]\n",
    "        for i in range(len(edges)):\n",
    "            x,y=edges[i]\n",
    "            if find(x-1)==find(y-1):\n",
    "                res=edges[i]\n",
    "            else:\n",
    "                union(x-1,y-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, size):\n",
    "        self.pa = [i for i in range(size)]\n",
    "        self.size = [1] * size\n",
    "\n",
    "    def search(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.search(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.search(x), self.search(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.pa[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "\n",
    "    def check_connected(self, x, y):\n",
    "        x, y = self.search(x), self.search(y)\n",
    "        return x == y\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = edges.__len__()\n",
    "        dsu = Dsu(n)\n",
    "        for x, y in edges:\n",
    "            if dsu.check_connected(x - 1, y - 1):\n",
    "                return [x, y]\n",
    "            dsu.union(x - 1, y - 1)\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, root_x, root_y):\n",
    "        if self.rank[root_x] > self.rank[root_y]:\n",
    "            self.parent[root_y] = root_x\n",
    "        else:\n",
    "            self.parent[root_x] = root_y\n",
    "            if self.rank[root_x] == self.rank[root_y]:\n",
    "                self.rank[root_y] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        ufs = UnionFindSet(n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            root_a = ufs.find(a-1)\n",
    "            root_b = ufs.find(b-1)\n",
    "            if root_a == root_b:\n",
    "                return [a, b]\n",
    "            ufs.union(root_a, root_b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getfather(self, num: int) -> int:\n",
    "        while num != self.fathers[num]:\n",
    "            num = self.fathers[num]\n",
    "\n",
    "        return num\n",
    "\n",
    "    def join(self, x: int, y: int) -> bool:\n",
    "        xf = self.getfather(x)\n",
    "        yf = self.getfather(y)\n",
    "        self.fathers[yf] = xf\n",
    "        return xf == yf\n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.fathers = [i for i in range(len(edges) + 1)]\n",
    "        redund = [None]\n",
    "\n",
    "        for i, v in enumerate(edges):\n",
    "            if self.join(v[0], v[1]):\n",
    "                redund.append(v)\n",
    "        return redund[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)  \n",
    "        res=[]    \n",
    "        for i in range(n):# 丢掉第n个\n",
    "            connect=[[] for _ in range(n)]\n",
    "            for j,edge in enumerate(edges):\n",
    "                if j==i:\n",
    "                    continue\n",
    "                connect[edge[0]-1].append(edge[1]-1)\n",
    "                connect[edge[1]-1].append(edge[0]-1)\n",
    "            seen=[False]*n\n",
    "            q=collections.deque([0])\n",
    "            while q:\n",
    "                cur= q.popleft()\n",
    "                seen[cur]=True\n",
    "                for node in connect[cur]:\n",
    "                    if seen[node]==False and not(node in q):\n",
    "                        q.append(node)\n",
    "            if sum(seen)==n:\n",
    "                res=edges[i]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(index: int) -> int:\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UF(len(edges)+1)\n",
    "        for edge in edges:\n",
    "            if(uf.isConnected(edge[0], edge[1])):\n",
    "                return edge\n",
    "            uf.merge(edge[0], edge[1])\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.father = [x for x in range(n)]\n",
    "    def find(self, x):\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    def merge(self, x, y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "    def isConnected(self, x, y) -> bool:\n",
    "        return self.find(x) == self.find(y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        parents = [x for x in range(n+1)]\n",
    "\n",
    "        def find(idx):\n",
    "            if parents[idx] != idx:\n",
    "                parents[idx] = find(parents[idx])\n",
    "            return parents[idx]\n",
    "        \n",
    "        def union(idx1, idx2):\n",
    "            parents[find(idx1)] = find(idx2)\n",
    "        \n",
    "        for node1, node2 in edges:\n",
    "            if find(node1) != find(node2):\n",
    "                union(node1, node2)\n",
    "            else:\n",
    "                return [node1, node2]\n",
    "        \n",
    "        return []\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        p = list(range(n + 1))\n",
    "        \n",
    "        def search(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = search(p[i])\n",
    "            return p[i]\n",
    "        \n",
    "        def union(i, j):\n",
    "            p[search(i)] = search(j)\n",
    "        \n",
    "        for i, j in edges:\n",
    "            if search(i) != search(j):\n",
    "                union(i, j)\n",
    "            else:\n",
    "                return [i,j]\n",
    "        return []\n",
    "        \n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    #路径压缩，针对qucik union 并查集\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n+1))\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])  # 路径压缩\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        \n",
    "        if root_x != root_y:\n",
    "            self.parent[root_y] = root_x\n",
    "    \n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        union = UnionFind(len(edges))\n",
    "        for x,y in edges:\n",
    "            if not union.is_connected(x, y):\n",
    "                union.union(x, y)\n",
    "            else:\n",
    "                return [x,y]\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)+1\n",
    "        par=[i for i in range(n)]   \n",
    "        def find(x):\n",
    "            if x==par[x]:\n",
    "                return x\n",
    "            return find(par[x])\n",
    "        def un(x,y):\n",
    "            rootx,rooty=find(x),find(y)\n",
    "            if rootx==rooty:\n",
    "                return False\n",
    "            par[rootx]=rooty\n",
    "            return True\n",
    "        for x,y in edges:\n",
    "            if un(x,y)==False:\n",
    "                return [x,y]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        ### prim\n",
    "        # n = len(edges)\n",
    "        # from collections import defaultdict\n",
    "        # import heapq\n",
    "        # import copy\n",
    "        # edge_q = []\n",
    "        # graph = defaultdict(list)\n",
    "        # for w, e in enumerate(edges): #### 权重\n",
    "        #     graph[e[0]].append([e[1], w])\n",
    "        #     graph[e[1]].append([e[0], w])\n",
    "\n",
    "        \n",
    "        # visited = [False] * n\n",
    "        # edges_copy = copy.deepcopy(edges) \n",
    "        # for i in range(n):\n",
    "        #     if not visited[i]:\n",
    "        #         visited[i] = True\n",
    "        #         for neighbor in graph[i+1]:\n",
    "        #             if not visited[neighbor[0]-1]:\n",
    "        #                 triple = [neighbor[1], i+1, neighbor[0]]\n",
    "        #                 heapq.heappush(edge_q, triple)\n",
    "                    \n",
    "        #         while len(edge_q):\n",
    "        #             triple = heapq.heappop(edge_q)\n",
    "        #             if visited[triple[2]-1]:\n",
    "        #                 continue\n",
    "                    \n",
    "        #             visited[triple[2]-1] = True\n",
    "        #             edges_copy.remove([min(triple[1:]), max(triple[1:])])\n",
    "        #             node =  triple[2]\n",
    "        #             for neighbor in graph[node]:\n",
    "        #                 if not visited[neighbor[0]-1]:\n",
    "        #                     triple = [neighbor[1], node, neighbor[0]]\n",
    "        #                     heapq.heappush(edge_q, triple)\n",
    "        \n",
    "        # return edges_copy[0]\n",
    "\n",
    "\n",
    "        #### kruskal\n",
    "        n = len(edges)\n",
    "        set_color = [i for i in range(n)]\n",
    "        color_dict = {i: [i+1] for i in range(n)}\n",
    "        import heapq\n",
    "        edge_q = [[i, e] for i, e in enumerate(edges)]\n",
    "        heapq.heapify(edge_q)\n",
    "        while len(edge_q):\n",
    "            e = heapq.heappop(edge_q)[1]\n",
    "            if set_color[e[0]-1] == set_color[e[1]-1]:\n",
    "                continue\n",
    "            color0 = set_color[e[0]-1]\n",
    "            color1 = set_color[e[1]-1]\n",
    "            if len(color_dict[color1]) > len(color_dict[color0]):\n",
    "                for n in color_dict[color0]:\n",
    "                    set_color[n-1] = color1\n",
    "                color_dict[color1].extend(color_dict.pop(color0))\n",
    "            else:\n",
    "                for n in color_dict[color1]:\n",
    "                    set_color[n-1] = color0\n",
    "                color_dict[color0].extend(color_dict.pop(color1))\n",
    "\n",
    "            edges.remove(e)\n",
    "        \n",
    "        return edges[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        graph = defaultdict(set)\n",
    "        degrees = [0] * (n+1)\n",
    "        for a,b in edges:\n",
    "            graph[a].add(b)\n",
    "            graph[b].add(a)\n",
    "            degrees[a] += 1\n",
    "            degrees[b] += 1\n",
    "        \n",
    "        q = deque([i for i in range(1,n+1) if degrees[i] == 1])\n",
    "        seen = set()\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            seen.add(cur)\n",
    "            for j in graph[cur]:\n",
    "                graph[j].remove(cur)\n",
    "                degrees[j] -= 1\n",
    "                if degrees[j] == 1:\n",
    "                    q.append(j)\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            a,b = edges[i]\n",
    "            if a not in seen and b not in seen:\n",
    "                return edges[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        row = len(edges)\n",
    "        parent = list(range(row + 1))\n",
    "\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            set_x = find(x)\n",
    "            set_y = find(y)\n",
    "            if set_x != set_y:\n",
    "                parent[set_x] = set_y\n",
    "            \n",
    "        for i, j in edges:\n",
    "            if find(i) == find(j):\n",
    "                return [i, j]\n",
    "            else:\n",
    "                union(i, j)\n",
    "        return [0, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n=len(edges)\n",
    "        kkk=setUnion(n+1)\n",
    "        for i,j in edges:\n",
    "            if kkk.find(i)==kkk.find(j): return [i,j]\n",
    "            kkk.union(i,j)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "    def add(self, x):\n",
    "        self.parent[x] = x\n",
    "        self.size[x] = 1\n",
    "        self.cnt += 1\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        \n",
    "        return self.parent[x]\n",
    "    \n",
    "    def connect(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        if self.connect(p, q): return \n",
    "\n",
    "        leader_p, leader_q = self.find(p), self.find(q)\n",
    "        \n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "            del self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "            del self.size[leader_q]\n",
    "        \n",
    "        self.cnt -= 1\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        uf = UF()\n",
    "        for i in range(1, n+1): \n",
    "            uf.add(i)\n",
    "\n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            if uf.connect(a, b): \n",
    "                return [a, b]\n",
    "            else:\n",
    "                uf.union(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        class union_finder:\n",
    "            def __init__(self, n) -> None:\n",
    "                self.root = [i for i in range(n)]\n",
    "                self.rank = [0 for i in range(n)]\n",
    "\n",
    "            def find(self, x):\n",
    "                if x == self.root[x]:\n",
    "                    return x\n",
    "                rootX = self.find(self.root[x])\n",
    "                self.root[x] = rootX\n",
    "                return rootX\n",
    "\n",
    "            def is_connect(self, x, y):\n",
    "                rootX = self.find(x)\n",
    "                rootY = self.find(y)\n",
    "                return rootX == rootY\n",
    "\n",
    "            def union(self, x, y):\n",
    "                rootX = self.find(x)\n",
    "                rootY = self.find(y)\n",
    "                if self.rank[rootX] > self.rank[rootY]:\n",
    "                    self.root[rootY] = rootX\n",
    "                elif self.rank[rootY] > self.rank[rootX]:\n",
    "                    self.root[rootX] = rootY\n",
    "                else:\n",
    "                    self.rank[rootX] += 1\n",
    "                    self.root[rootY] = rootX\n",
    "        n = len(edges)\n",
    "        finder = union_finder(n)\n",
    "        \n",
    "        vis = set()\n",
    "        for i, edge in enumerate(edges):\n",
    "            x, y = edge\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            if not finder.is_connect(x, y):\n",
    "                finder.union(x, y)\n",
    "                vis.add(i)\n",
    "        \n",
    "        return edges[list(set(range(n)) - vis)[0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, M):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "        for node in M:\n",
    "            self.parent[node] = node\n",
    "            self.cnt += 1\n",
    "            self.size[node] = 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        \n",
    "        return self.parent[x]\n",
    "        \n",
    "\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        # 小的树挂到大的树上， 使树尽量平衡\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        self.cnt -= 1\n",
    "\n",
    "        \n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        M = [i for i in range(1,n+1)]\n",
    "        uf = UF(M)\n",
    "        for edge in edges:\n",
    "            p, q = edge\n",
    "            if not uf.connected(p, q):            # NOTE 无向图的连通块\n",
    "                uf.union(p, q)\n",
    "            else:                                 # NOTE 检查到了环\n",
    "                return [p, q]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        class Node:\n",
    "            def __init__(self):\n",
    "                self.parent = None\n",
    "        def merge(a, b):\n",
    "            aa = query(a)\n",
    "            bb = query(b)\n",
    "            bb.parent = aa\n",
    "        def query(a):\n",
    "            while a.parent:\n",
    "                a = a.parent\n",
    "            return a\n",
    "\n",
    "        mx = 0\n",
    "        for ii in edges:\n",
    "            for i in ii:\n",
    "                mx = max(mx, i)\n",
    "\n",
    "        node_list = [Node() for _ in range(mx+1)]\n",
    "\n",
    "        for edge in edges:\n",
    "            if query(node_list[edge[0]]) == query(node_list[edge[1]]):\n",
    "                return edge\n",
    "            else:\n",
    "                merge(node_list[edge[0]], node_list[edge[1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = 1\n",
    "        for idx1, idx2 in edges:\n",
    "            if idx1 > idx2 and idx1 > n:\n",
    "                n = idx1\n",
    "            elif idx2 > idx1 and idx2 > n:\n",
    "                n = idx2\n",
    "        \n",
    "        parent = {idx: idx for idx in range(1, n + 1)}\n",
    "\n",
    "        def find(i):\n",
    "            if parent[i] != i:\n",
    "                return find(parent[i])\n",
    "            else:\n",
    "                return i\n",
    "        \n",
    "        def merge(i, j):\n",
    "            parent[find(i)] = find(j)\n",
    "\n",
    "\n",
    "        for i, j in edges:\n",
    "            if find(i) != find(j):\n",
    "                merge(i, j)\n",
    "            else:\n",
    "                return [i, j]\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "    def add(self, x):\n",
    "        self.parent[x] = x\n",
    "        self.size[x] = 1\n",
    "        self.cnt += 1\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        \n",
    "        return self.parent[x]\n",
    "    \n",
    "    def connect(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        if self.connect(p, q): return \n",
    "\n",
    "        leader_p, leader_q = self.find(p), self.find(q)\n",
    "        \n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "            del self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "            del self.size[leader_q]\n",
    "        \n",
    "        self.cnt -= 1\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        uf = UF()\n",
    "        n = len(edges)\n",
    "        for i in range(1, n+1):\n",
    "            uf.add(i)\n",
    "        \n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            if uf.connect(a, b):\n",
    "                return [a, b]\n",
    "            uf.union(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val, parent = None):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "\n",
    "class Solution:\n",
    "    def add(self, val):\n",
    "\n",
    "        self.nodes[val] = Node(val)\n",
    "\n",
    "        return\n",
    "\n",
    "    def findRoot(self, node):\n",
    "        if not node.parent:\n",
    "            return node\n",
    "\n",
    "        root = node\n",
    "        while root.parent:\n",
    "            root = root.parent\n",
    "\n",
    "        while node != root:\n",
    "            tmp = node.parent\n",
    "            node.parent = root\n",
    "            node = tmp\n",
    "\n",
    "        return root\n",
    "\n",
    "    def merge(self, A, B, remove_list):\n",
    "        root_A = self.findRoot(A)\n",
    "        root_B = self.findRoot(B)\n",
    "\n",
    "        if root_A == root_B:\n",
    "            remove_list.append([A.val, B.val])\n",
    "            return \n",
    "\n",
    "        root_A.parent = root_B\n",
    "        \n",
    "\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        self.nodes = dict()\n",
    "        \n",
    "        res = []\n",
    "        for val_A, val_B in edges:\n",
    "            if val_A not in self.nodes:\n",
    "                self.add(val_A)\n",
    "            \n",
    "            if val_B not in self.nodes:\n",
    "                self.add(val_B)\n",
    "\n",
    "            A = self.nodes[val_A]\n",
    "            B = self.nodes[val_B]\n",
    "            self.merge(A, B, res)\n",
    "\n",
    "        return res[-1] if res else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        Hashtable = defaultdict(lambda :set())\n",
    "        Hashtable[0].clear()\n",
    "        Hashtable[1].clear()\n",
    "\n",
    "        for i in range(n):\n",
    "            inflag0 , inflag1 = False ,False\n",
    "            inflagi0, inflagi1 = -1, -1\n",
    "            for key , val in Hashtable.items():\n",
    "                if edges[i][0] in val:\n",
    "                    inflag0 = True\n",
    "                    inflagi0 = key\n",
    "                if edges[i][1] in val:\n",
    "                    inflag1 = True\n",
    "                    inflagi1 = key\n",
    "                if inflag0 and inflag1:\n",
    "                    break\n",
    "\n",
    "            if not inflag0 and not inflag1:\n",
    "                for k in range(n):\n",
    "                    if Hashtable[k] == set():\n",
    "                        Hashtable[k].add(edges[i][0])\n",
    "                        Hashtable[k].add(edges[i][1])\n",
    "                        break\n",
    "            elif inflag0 and inflag1:\n",
    "                if inflagi0 == inflagi1:\n",
    "                    return edges[i]\n",
    "                else:\n",
    "                    Hashtable[inflagi0] = Hashtable[inflagi0] | Hashtable[inflagi1]\n",
    "                    Hashtable[inflagi1].clear()\n",
    "            else:\n",
    "                if inflag0:\n",
    "                    Hashtable[inflagi0].add(edges[i][1])\n",
    "                else:\n",
    "                    Hashtable[inflagi1].add(edges[i][0])\n",
    "            # print(Hashtable.items())\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        ### prim\n",
    "        n = len(edges)\n",
    "        from collections import defaultdict\n",
    "        import heapq\n",
    "        import copy\n",
    "        edge_q = []\n",
    "        graph = defaultdict(list)\n",
    "        for w, e in enumerate(edges): #### 权重\n",
    "            graph[e[0]].append([e[1], w])\n",
    "            graph[e[1]].append([e[0], w])\n",
    "\n",
    "        \n",
    "        visited = [False] * n\n",
    "        edges_copy = copy.deepcopy(edges) \n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = True\n",
    "                for neighbor in graph[i+1]:\n",
    "                    if not visited[neighbor[0]-1]:\n",
    "                        triple = [neighbor[1], i+1, neighbor[0]]\n",
    "                        heapq.heappush(edge_q, triple)\n",
    "                    \n",
    "                while len(edge_q):\n",
    "                    triple = heapq.heappop(edge_q)\n",
    "                    if visited[triple[2]-1]:\n",
    "                        continue\n",
    "                    \n",
    "                    visited[triple[2]-1] = True\n",
    "                    edges_copy.remove([min(triple[1:]), max(triple[1:])])\n",
    "                    node =  triple[2]\n",
    "                    for neighbor in graph[node]:\n",
    "                        if not visited[neighbor[0]-1]:\n",
    "                            triple = [neighbor[1], node, neighbor[0]]\n",
    "                            heapq.heappush(edge_q, triple)\n",
    "        \n",
    "        return edges_copy[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        n = len(edges)\n",
    "        for edge in edges:\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "        for edge in edges[::-1]:\n",
    "            graph[edge[0]].remove(edge[1])\n",
    "            graph[edge[1]].remove(edge[0])\n",
    "            visited = [0 for i in range(n)]\n",
    "            if self.dfs_find(graph,edge[0],edge[1],visited):\n",
    "                return edge\n",
    "            graph[edge[0]].append(edge[1])\n",
    "            graph[edge[1]].append(edge[0])\n",
    "\n",
    "\n",
    "    def dfs_find(self,graph:Dict[int,List[int]],cur:int,target:int,visited:List[int]):\n",
    "        if visited[cur-1]:\n",
    "            return\n",
    "        if cur == target:\n",
    "            return True\n",
    "        visited[cur-1] = True\n",
    "        for next_point in graph[cur]:\n",
    "            if self.dfs_find(graph,next_point,target,visited):\n",
    "                return True\n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n",
    "        n = len(edges)\n",
    "        l = list(range(1,n+1))\n",
    "        node2set = dict(zip(l, l))\n",
    "        set2node = {}\n",
    "        for i in range(n):\n",
    "            set2node[i+1] = [i+1]\n",
    "        \n",
    "        for node1, node2 in edges:\n",
    "\n",
    "            if node2set[node1] == node2set[node2]:\n",
    "                return [node1, node2]\n",
    "            # print(set2node[node2set[node2]])\n",
    "            for node in set2node[node2set[node2]]:\n",
    "                node2set[node] = node2set[node1]\n",
    "                set2node[node2set[node1]].append(node)\n",
    "            # print(node2set)\n",
    "            # print(set2node)\n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
